package com.kuang.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author kjx
 */


/*  给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。 */
public class InorderTraversal {



    //第一种是常规的递归，这个result你放到外面也行，如果实践使用，就再封装一个函数就行，不会暴露出去的
    //我这里省事就丢到外面去了
    List<Integer> result = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) {
            return new ArrayList<>();
        }
        inorderTraversal(root.left);
        result.add(root.val);
        inorderTraversal(root.right);

        return result;
    }



    //第二种就是循环，这种纯递归的一般用栈都能做，用纯循环可能有点困难
    public List<Integer> inorderTraversal2(TreeNode root){
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()){
            while (root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }



}
